""" 针对 英文状态的单词
输入：2 6 6 5 6 8 7
输出：bonjour
"""
"""
这个问题实例的第一部分是一个字典结构，由一系列键值对 (m, w) 组成，
其中 m 是一个由 26 个小写字母中部分字母组成的单词，w 是这个单词的权重。
问题实例的第二部分由输入序列为 2 ～ 9 的数字组成。
对于每个输入序列，只需要显示字典中权重最高的一个单词。

假设有一个数字序列使用 T9 输入法，根据九键输入法中的对应关系，
输出单词为 m，而输入数字序列 t 是通过将单词 m中的每个字母都替换为相关数字得来的。
s 是输入数字序列 t 的前缀，
这时，我们就可以定义单词 m 与 s 相关。
比如单词 bonjour（你好）与数字序列 26 相关，也和数字序列 266 或 2665687 相关。

--------

字典初始化的时间复杂度为 O(nk)，而每次查询的时间复杂度为 O(k)。
这里的 n 是字典中的单词数量，k 是单词长度的上限。

在第一时间，对于字典中某个单词的每个前缀 p ， 
(这里可以理解为，每次用 T9 输入法输入一个新数字的时候，由于尚未输入完成，输入数字序列的前几个数字就是整个输入序列的前缀。)
我们要查找将 p 作为前缀的所有单词的总权重，
并把总权重存入一个 freq（频率）字典中。

接下来，我们在另一个字典 prop[seq] 中存储赋予每个给定的 seq 序列的前缀列表。
遍历 freq 中的所有键，可以确定权重最大的前缀。
此处的关键就是 word_code 函数，它能为给定单词提供相关的输入数字序列。
"""

# 分别对应 abc def ghi jkl mno pqrs tuv wxyz 这 26 个字母
t9 = "22233344455566677778889999"


def letter_digit(x):
    """根据字母返回九键中对应的数字"""
    assert 'a' <= x <= 'z'
    return t9[ord(x) - ord('a')]


def word_code(words):
    return ''.join(map(letter_digit, words))


def predictive_text(dic):  # dic 意为字典
    """
    主要部分
    :param dic: 记录 单词-权重 的 字典
    :return: 权重最大的 前缀-单词 字典
    """
    # freq[p] = 拥有前缀 p 的单词的总权重
    freq = {}
    for words, weights in dic.items():
        prefix = ""
        for x in words:
            prefix += x
            if prefix in freq:
                freq[prefix] += weights
            else:
                freq[prefix] = weights

    # prop[s] = 输入 s 时要显示的前缀
    prop = {}
    for prefix in freq:
        code = word_code(prefix)
        if code not in prop or freq[prop[code]] < freq[prefix]:
            prop[code] = prefix
    return prop


def propose(prop, seq):
    """根据权重字典匹配权重最高的单词"""
    if seq in prop:
        return prop[seq]
    else:
        return "None"


if __name__ == '__main__':
    dic = {
        "bonjour": 10,
        "anolmus": 8,
    }
    seq = "2665687"
    prop = predictive_text(dic)
    print(prop)
    word = propose(prop, seq)
    print(word)
